UP (complexidade) - definition. What is UP (complexidade)
Diclib.com
قاموس ChatGPT
أدخل كلمة أو عبارة بأي لغة 👆
اللغة:

ترجمة وتحليل الكلمات عن طريق الذكاء الاصطناعي ChatGPT

في هذه الصفحة يمكنك الحصول على تحليل مفصل لكلمة أو عبارة باستخدام أفضل تقنيات الذكاء الاصطناعي المتوفرة اليوم:

  • كيف يتم استخدام الكلمة في اللغة
  • تردد الكلمة
  • ما إذا كانت الكلمة تستخدم في كثير من الأحيان في اللغة المنطوقة أو المكتوبة
  • خيارات الترجمة إلى الروسية أو الإسبانية، على التوالي
  • أمثلة على استخدام الكلمة (عدة عبارات مع الترجمة)
  • أصل الكلمة

%ما هو (من)٪ 1 - تعريف


UP (complexidade)         
Na teoria da complexidade, UP ("Tempo Polinomial Não-determinístico Não-ambíguo") é a classe de complexidade dos problemas de decisão resolvidos em tempo polinomial em uma máquina de Turing não ambígua com, no máximo, uma caminho de aceitação para cada entrada. UP contém P e está contida em NP.
Complexidade ciclomática         
Complexidade ciclomática (ou complexidade condicional) é uma métrica de software usada para indicar a complexidade de um programa de computador. Desenvolvida por Thomas J.
Complexidade fatorial         
Representada por O(n!), é normalmente encontrada ao analisar a complexidade de algoritmos de força bruta, que tentam todas as possibilidades para problemas de otimização combinatória.

ويكيبيديا

UP (complexidade)

Na teoria da complexidade, UP ("Tempo Polinomial Não-determinístico Não-ambíguo") é a classe de complexidade dos problemas de decisão resolvidos em tempo polinomial em uma máquina de Turing não ambígua com, no máximo, uma caminho de aceitação para cada entrada. UP contém P e está contida em NP.

Uma reformulação costumeira de NP afirma que uma linguagem está em NP se e somente se uma determinada resposta pode ser verificada por uma máquina determinística em tempo polinomial. Da mesma forma, uma linguagem está em UP, se uma dada resposta pode ser verificada em tempo polinomial, e a máquina verificadora só aceita no máximo uma resposta para cada instância do problema. Mais formalmente, uma linguagem L pertence a UP se existe um algoritmo de tempo polinomial A de duas entradas e uma constante c tal que

se x está em L , então existe um único certificado y com | y | = O ( | x | c ) {\displaystyle |y|=O(|x|^{c})} de tal forma que A ( x , y ) = 1 {\displaystyle A(x,y)=1}
se x não está em L, não há nenhum certificado de y com | y | = O ( | x | c ) {\displaystyle |y|=O(|x|^{c})} de tal forma que A ( x , y ) = 1 {\displaystyle A(x,y)=1}
o algoritmo A verifica L em tempo polinomial.

UP (e seu complemento co-UP) contêm os problemas de fatoração de inteiros e do jogo de paridade; em razão do fato de que determinado esforço ainda tem que ser feito para encontrar uma solução em tempo-polinômial para qualquer um desses problemas, suspeita-se ser difícil mostrar que P=UP, ou mesmo P=(UPco-UP).

O Teorema de Valiant-Vazirani  afirma que NP está contida em RPPromise-UP, o que significa que há uma redução aleatorizada de qualquer problema em NP para um problema em Promise-UP.

Não se sabe se UP tem algum problema completo.